package com.tgy.tree;

import com.tgy.util.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Stack;



/**
 * @Author: tgy
 * @Date: 2020-09-12 09:52
 */
public class BinarySearchTreeRetry<E> extends BinaryTree<E> {


    private Comparator<E> comparator;

    public BinarySearchTreeRetry() {

    }

    public BinarySearchTreeRetry(Comparator<E> comparator) {

        this.comparator = comparator;
    }

    public void add(E element) {

        if (element == null) {

            return;
        }

        if (root == null) {

            root = new Node<>(element, root);
            return;
        }


        Node<E> node = root;

        Node<E> parentNode = null;
        int result = 0;

        while (node != null) {

            result = compare(element,node.element);

            parentNode = node;

            if (result < 0) {

                node = node.left;
            }else if (result > 0) {

                node = node.right;
            }else {

//                相等则替换
                node.element = element;
                return;
            }
        }

        Node<E> newNode = new Node<>(element, parentNode);
        if (result < 0) {

//            放left
            parentNode.left = newNode;
        }else if (result > 0) {

//            放left
            parentNode.right = newNode;
        }

        size++;
    }

    public Node<E> remove(E element) {

        Node<E> node = inorderTaversalTree(element);

        if (node == null) {

            return null;
        }

        if (node.degree() == 2) {

            Node<E> nextNode = nextNode(node);

            E tmpElement = node.element;
            node.element = nextNode.element;
            node = nextNode;
            node.element = tmpElement;
        }

        if (node.degree() == 0) {


            if (node.parent != null) {

                if (node.equals(node.parent.left)) {

                    node.parent.left = null;
                }else {

                    node.parent.right = null;
                }


            }else {

                root = null;
            }

        }else {

            if (node.parent != null) {


                if (node.equals(node.parent.left)) {

                    node.parent.left = node.left != null?node.left:node.right;

                    node.parent.left.parent = node.parent;

                }else {

                    node.parent.right = node.left != null?node.left:node.right;

                    node.parent.right.parent = node.parent;
                }



            }else {

                root = node.left != null?node.left:node.right;

                root.parent = null;
            }


        }

        size--;
        return node;
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder("size=");

        sb.append(size).append(" {\n");

        sb.append(levelTraversalTree());
//        sb.append(postinderTraversalTree());

        sb.append("\n}");

        return sb.toString();
    }

    /**
     * 比较两个节点元素的大小
     * @param left
     * @param right
     * @return
     */
    private int compare(E left, E right) {

        if (this.comparator != null) {

            return comparator.compare(left,right);
        }

        return  ((Comparable<E>)left).compareTo(right);
    }

}
